from datetime import datetime
from math import fabs
import random

from grid import BasicGrid, SnakeContainer
from snake import BasicSnake
from globals import *

# There is a special case when snake.totalLength == 1.
# This case is supported but requires some additional
# code, which is not really pretty. Maybe there is a
# way to include this case implicitly.
# Note that if snake.totalLength == 2, it can go
# "through" itself. This behaviour seems to be
# wrong but is acceptable product of our algorithm.
# If desired, it could be handled by a little code
# when detecting crashes.
# Other case works as expected.

# snake composed of line segments
class AISnake:
	def __init__(self, basicSnake):
		self.template = basicSnake
		self.isHuman = basicSnake.isHuman
		self.length = len(basicSnake.segments)
		self.totalLength = basicSnake.totalLength
		self.symbol = basicSnake.symbol
		self.direction = basicSnake.direction
		self.lsegments = []
		self.head = basicSnake.segments[-1]
		# convert discrete segments into line segments
		for i in xrange(self.length-2, -1, -1):
			newHead = basicSnake.segments[i]
			self.addNewHead(newHead)

	# creates new line segment or extends existing
	def addNewHead(self, newHead):
		unitVec = tuple(subZip (newHead) (self.head))
		if self.lsegments == [] or self.lsegments[0][2] != unitVec:
			self.lsegments.insert(0, [newHead, self.head, unitVec])
		else:
			self.lsegments[0][0] = newHead
		self.head = newHead
	
	def removeTail(self):
		last = self.lsegments[-1]
		last[1] = addZip (last[1]) (last[2])
		if last[0] == last[1]:
			lsegment = self.lsegments.pop(-1)

	def update(self):
		newHead = addZip (self.head) (MOVEMODS[self.direction])
		self.addNewHead(newHead)
		self.length += 1
		# remove old tail
		if self.length == self.totalLength + 1:
			self.removeTail()
			self.length -= 1

# continuous grid that enables usage of continuous bfs to
# calculate voronoi territories. Kept in sync with gameGrid.
class AIGrid:
	def __init__(self, gridWalls, gameSnakes):
		self.snakes = [] # order of snakes is going to be fixed
		self.gridWalls = gridWalls
		for snake in gameSnakes:
			if snake.isAlive:
				self.snakes.append(AISnake(snake))

	def isCrashed(self, snake, wall):
		if snake.lsegments != []: # snake has length > 1
			# prevent head being crashed with its own lsegment
			if snake.lsegments[0] == wall:
				return False
		else: # snake has length == 1
			# prevent head being crashed with itself
			if [snake.head, snake.head, snake] == wall:
				return False

		hx  = snake.head[0]
		hy  = snake.head[1]
		w0x = wall[0][0]
		w0y = wall[0][1]
		w1x = wall[1][0]
		w1y = wall[1][1]
		if hx == w0x and hy >= min(w0y, w1y) and hy <= max(w0y, w1y):
			return True
		if hy == w0y and hx >= min(w0x, w1x) and hx <= max(w0x, w1x):
			return True
		return False
		
	def update(self):
		# update snakes 
		for snake in self.snakes:
			snake.update()

		# check for collisions
		# TODO: make quad tree of grid, solve collisions on it
		# TODO: probably exclude case when snake.totalLenght == 1,
		#	it makes code messy, or rethink the way we work
		#	with lsegments.
		walls = []
		walls += self.gridWalls
		for snake in self.snakes:
			if snake.lsegments != []:
				walls += snake.lsegments
			else:
				# snake has only head (no lsegments) but we still 
				# want to recognize crashes with it. This happens 
				# only if snake.totalLength == 1.
				walls.append([snake.head, snake.head, snake])

		# If a snake crashes, it is removed from self.snakes and hence,
		# we need to keep information on which position it was stored 
		# for its later adding back (relevant if called from negamax).
		crashedSnakes = []
		index = 0 
		for snake in self.snakes:
			for wall in walls:
				if self.isCrashed(snake, wall):
					crashedSnakes.append((index, snake))
					break
			index += 1
		
		for index, snake in crashedSnakes:
			self.snakes.remove(snake)
		return crashedSnakes


# AI works with relative moves (STRAIGHT, RIGHT, LEFT)
class AI:
	def __init__ (self, walls, gameGrid): # TODO: we need whole gameGrid only for debug, snakes are enough
		self.gameGrid = gameGrid
		self.grid = AIGrid(walls, gameGrid.snakes)
		self.botsMoveOpts = []
		self.humansMoveOpts = []
		self.bestBotsMove = None
		self.aliveBotsCount = 0
		self.aliveHumansCount = 0
		for snake in self.grid.snakes:
			if snake.isHuman:
				self.aliveHumansCount += 1
			else:
				self.aliveBotsCount += 1
		for cnt in xrange(self.aliveBotsCount+1):
			self.botsMoveOpts.append([])
			self.generateMoves(self.botsMoveOpts[cnt], cnt)
		for cnt in xrange(self.aliveHumansCount+1):
			self.humansMoveOpts.append([])
			self.generateMoves(self.humansMoveOpts[cnt], cnt)
		#self.startingTime = 0 # time when negamax started
		#self.timelimit = 0 # how long it can run

	#FIXME: unusuable atm
	def getTerritories(self):
		return self.voronoi()

	# pregenerate all possible relative moves of a team of 
	# snakes of teamSize or less members (humans or bots)
	# e.g. for two snakes there are 9 posibilites
	def generateMoves(self, moveList, teamSize):
		del moveList[:]
		if teamSize <= 0: 
			moveList.append([])
			return

		moveGen = [[move] for move in RELMOVES]

		while len(moveGen) != 0:
			partialMove = moveGen.pop(0)
			if len(partialMove) == teamSize:
				moveList.append(partialMove)
				continue
			for move in RELMOVES:
				moveGen.append([elem for elem in partialMove]+[move])

	def setMoves(self, botsMove, humansMove):
		# store current state of snakes
		snakeRecords = [] # [(direction, length, head, last segment), ...]
		for snake in self.grid.snakes:
			oldTail = None
			if snake.length == snake.totalLength and snake.lsegments != []:
				oldTail = snake.lsegments[-1][:]
			snakeRecords.append((snake.direction, snake.length, snake.head, oldTail))

		# set and apply moves (directions) of snakes
		botIndex = 0
		humanIndex = 0
		for snake in self.grid.snakes:
			if snake.isHuman:
				snake.direction = convertDirection (snake.direction) (humansMove[humanIndex])
				humanIndex += 1
			else:
				snake.direction = convertDirection (snake.direction) (botsMove[botIndex])
				botIndex += 1
		return snakeRecords 

	# reverting changes made by update()
	def revertMoves(self, snakeRecords, crashedSnakes):
		# Note that crashedSnakes are ordered by index in
		# ascending order implicitly. That assures we insert 
		# snakes back to their correct positions.
		for index, snake in crashedSnakes:
			self.grid.snakes.insert(index, snake)
		
		for index, snake in enumerate(self.grid.snakes):
			snakeRecord = snakeRecords[index]
			snake.direction = snakeRecord[0]
			snake.length = snakeRecord[1]
			snake.head = snakeRecord[2]
			oldTail = snakeRecord[3]
			
			if oldTail != None:
				x1, y1 = oldTail[0]
				x2, y2 = oldTail[1]
				if fabs(x2-x1) == 1 or fabs(y2-y1) == 1:
					snake.lsegments.append(oldTail)
				else:
					tail = snake.lsegments[-1]
					tail[1] = subZip (tail[1]) (tail[2])
			
			if snake.lsegments != []:
				head = snake.lsegments[0]
				x1, y1 = head[0]
				x2, y2 = head[1]
				if fabs(x2-x1) == 1 or fabs(y2-y1) == 1:
					snake.lsegments.pop(0)
				else:
					head[0] = subZip (head[0]) (head[2])

	# FIXME: unusuable atm
	# TODO: this algorithm is very very slow and unusable as part of evaluation
	# of negamax leaves. Find something much more faster.
	# get size of voronoi territory for each snake and return them
	# bfs variant with a queue for each snake and taking turns
	def voronoi(self):
		retSizes = [0 for snake in self.snakes]
		gridMap = [[0 for y in xrange(self.grid.size[1])] for x in xrange(self.grid.size[0])]
		expandedPrevs = [(1 if snake.isAlive else 0) for snake in self.snakes]
		ques = [([snake.segments[0]] if snake.isAlive else []) for snake in self.snakes]

		empty = False
		while not empty:
			index = 0
			for que in ques:
				processed = 0
				expandedPrev = expandedPrevs[index]
				expandedPrevs[index] = 0
				while processed < expandedPrev:
					head = que.pop(0)
					processed += 1
					if head == (-1, -1): # territory border, see code below
						retSizes[index] -= 1 # nobody's tile but has been counted
						continue 
					for move in MOVES:
						nextTile = addZip(head)(MOVEMODS[move])
						# if occupied or we have visited this tile before, continue
						if not self.grid.gmap[nextTile[0]][nextTile[1]].isEmpty() \
							or gridMap[nextTile[0]][nextTile[1]] & (1 << index) > 0: 
							continue
						que.append(nextTile)
						retSizes[index] += 1
						expandedPrevs[index] += 1
						# (1 << index) is a snake unique mark (footprint)
						gridMap[nextTile[0]][nextTile[1]] |= (1 << index)
				index += 1

			# Some tiles (territory borders) might have been visited 
			# by more than one snake. Set them to (-1, -1) for the
			# code above.
			for que in ques:
				for i in xrange(len(que)):
					tileVal = gridMap[que[i][0]][que[i][1]]
					setBits = 0
					while tileVal > 0:
						tileVal &= tileVal - 1 # clear the least significant bit set
						setBits += 1
					if setBits > 1:
						que[i] = (-1, -1)
			empty = True
			for que in ques:
				if len(que) > 0:
					empty = False
		# end while
		return retSizes, gridMap

	# evaluate current grid state (position)
	def evaluate(self):
		botsvsHumans = 0
		for snake in self.grid.snakes:
			if snake.isHuman: botsvsHumans -= 1
			else: botsvsHumans += 1
		
		botTerritory   = 0
		humanTerritory = 0
		"""
		retSizes, gridMap = self.voronoi()
		for i, retSize in enumerate(retSizes):
			if self.snakes[i].isHuman:
				humanTerritory += retSize
			else:
				botTerritory   += retSize
		"""
		return (botsvsHumans, botTerritory - humanTerritory)


	def outOfTime(self):
		timeDiff = (datetime.now() - self.startingTime).microseconds / 1000.0
		if  timeDiff > self.timelimit: 
			return True
		return False

	# TODO: iterating, calculating till timelimit
	def run(self, timelimit):
		if self.aliveBotsCount == 0:
			return

		self.bestBotsMove = self.botsMoveOpts[self.aliveBotsCount][0] # initial value to be reseted

		"""
		self.startingTime = datetime.now()
		self.timelimit = timelimit
		depth2reach = 3
		while True:
			self.negamax(0, depth2reach)
			depth2reach += 1
			if self.outOfTime(): break
		"""
		
		self.startingTime = datetime.now()
		self.negamax(0, 8, (-1E10, -1E10), (1E10, 1E10), [])
		#print self.negamax(0, 2, (-1E10, -1E10), (1E10, 1E10), []), RMOVESTRS[self.bestBotsMove[0]]
		#self.grid.dump()
		#print "-------------------------------"
		print (datetime.now() - self.startingTime).microseconds / 1000.0

	# lexicographical ordering operator on position values
	def greaterThan(self, v1, v2):
		return v1[0] > v2[0] or (v1[0] == v2[0] and v1[1] > v2[1])

	# lexicographical ordering operator on position values
	def greaterThanOrEqual(self, v1, v2):
		return v1[0] > v2[0] or (v1[0] == v2[0] and v1[1] >= v2[1])

	# FIXME: unusuable atm
	# move sorting according to count of crashes likely to happen
	# better moves should be examined first for algorithm to be faster
	def sortMoves(self, moveOptions, snakeTeam):
		sortList = []
		for moveOption in moveOptions:
			index = 0
			likelyDeaths = 0
			for snake in snakeTeam:
				if snake.isAlive:
					relMove = moveOption[index]
					absMove = convertDirection (snake.direction) (relMove)
					moveMod = MOVEMODS[absMove]
					x, y = addZip (snake.segments[0]) (moveMod)
					if not self.grid.gmap[x][y].isEmpty():
						likelyDeaths += 1
					index += 1
			index2 = 0
			for elem in sortList:
				if elem[0] >= likelyDeaths:
					sortList.insert(index2, (likelyDeaths, moveOption))
					break
				index2 += 1
			if index2 == len(sortList):
				sortList.append((likelyDeaths, moveOption))
		sortedMoveOptions = []
		for elem in sortList:
			sortedMoveOptions.append(elem[1])
		return sortedMoveOptions

	# search in depth for the best move using alpha-beta prunned negamax
	# depth2reach should be even (odd depth2reach gives the same as depth2reach - 1)
	def negamax(self, depth, depth2reach, alpha, beta, botsMove):
		if depth == depth2reach:
			return self.evaluate()

		values = []
		maxValue = (-1E10, -1E10) # (life diff, territory diff)
		isBotsMove = (depth % 2 == 0)

		if isBotsMove: 
			moveOptions = self.botsMoveOpts[self.aliveBotsCount]
			#snakeTeam = self.bots
		else:          
			moveOptions = self.humansMoveOpts[self.aliveHumansCount]
			#snakeTeam = self.humans
		
		# sorting moves for alpha beta
		#moveOptions = self.sortMoves(moveOptions, snakeTeam)

		# moves are applied only at odd depth (where both humans' and bots' move has been chosen)
		for move in moveOptions:
			if isBotsMove:
				# move is going to be applied one level below
				tmp = self.negamax(depth+1, depth2reach, (-beta[0], -beta[1]), (-alpha[0], -alpha[1]), move) 
				value = (-tmp[0], -tmp[1])
			else:
				snakeRecords  = self.setMoves(botsMove, move) # set moves
				crashedSnakes = self.grid.update() # apply moves

				# update counts of alive snakes and determine 
				# value of current position based on them
				crashedBotsCount   = 0
				crashedHumansCount = 0
				for index, snake in crashedSnakes:
					if snake.isHuman:
						crashedHumansCount += 1
					else:
						crashedBotsCount   += 1
				self.aliveBotsCount   -= crashedBotsCount
				self.aliveHumansCount -= crashedHumansCount
				currentLifeValue = self.aliveHumansCount - self.aliveBotsCount
				
				if alpha[0] > currentLifeValue or beta[0] < currentLifeValue:
					# alpha prunned based on current difference in snakes alive
					value = (currentLifeValue, 0)
				else:
					# regular position evaluation
					tmp = self.negamax(depth+1, depth2reach, (-beta[0], -beta[1]), (-alpha[0], -alpha[1]), []) # go deeper
					value = (-tmp[0], -tmp[1])
				
				self.revertMoves(snakeRecords, crashedSnakes) # revert moves
				# revert counts of alive snakes
				self.aliveBotsCount   += crashedBotsCount
				self.aliveHumansCount += crashedHumansCount

			# if self.outOfTime(): return 0
			
			# updating local alpha value
			if self.greaterThan(value, alpha):
				alpha = value
			
			# updating maxValue and best found move of bots
			if self.greaterThan(value, maxValue):
				maxValue = value
				if depth == 0:
					self.bestBotsMove = move
			
			#print "    " * (depth + 1), value, RMOVESTRS[move[0]] if len(move) > 0 else None

			# alpha beta prunning based on current difference in
			# snakes alive and also territory sizes counted in leaves
			if self.greaterThanOrEqual(alpha, beta):
				break
		return maxValue

	def moveBots(self):
		index = 0
		for snake in self.grid.snakes:
			if not snake.isHuman:
				absDir = convertDirection (snake.direction) (self.bestBotsMove[index])
				snake.template.direction = absDir
				index += 1

	# synchronize AIGrid with GameGrid
	def update(self):
		for aiSnake in self.grid.snakes:
			aiSnake.direction = aiSnake.template.direction
		crashedSnakes = self.grid.update()
		for index, snake in crashedSnakes:
			if snake.isHuman:
				self.aliveHumansCount -= 1
			else:
				self.aliveBotsCount -= 1
